class Solution {
public:
    int mySqrt(int x) 
    {
        if(x <= 1)
            return x;

        int low = 1;
        int height = x;

        while(low < height)
        {
            int mid = low + (low + height) / 2;

            if(mid == x / mid)
                return mid;
            else if(mid < x / mid)
                low = mid + 1;
            else height = mid - 1;
        }

        return height;
    }
};

//二分法查找